{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# The Perceptron Algorithm"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np \n",
    "np.set_printoptions(suppress=True)\n",
    "import matplotlib.pyplot as plt\n",
    "import seaborn as sns\n",
    "from sklearn import datasets\n",
    "\n",
    "# import data\n",
    "cancer = datasets.load_breast_cancer()\n",
    "X = cancer['data']\n",
    "y = cancer['target']"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Before constructing the perceptron, let's define a few helper functions. The `sign` function returns `1` for positive numbers and `-1` for non-positive numbers, which will be useful since the perceptron classifies according to \n",
    "\n",
    "$$\n",
    "\\text{sign}(\\bbeta^\\top \\bx_n).\n",
    "$$\n",
    "\n",
    "Next, the `to_binary` function can be used to convert predictions in $\\{-1, +1\\}$ to their equivalents in $\\{0, 1\\}$, which is useful since the perceptron algorithm uses the former though binary data is typically stored as the latter. Finally, the `standard_scaler` standardizes our features, similar to `scikit-learn`'s `StandardScaler`. \n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```{note}\n",
    "Note that we don't actually need to use the `sign` function. Instead, we could deem an observation correctly classified if $y_n \\hat{y}_n \\geq 0$ and misclassified otherwise. We use it here to be consistent with the derivation in the content section.\n",
    "```"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [],
   "source": [
    "def sign(a):\n",
    "    return (-1)**(a < 0)\n",
    "\n",
    "def to_binary(y):\n",
    "        return y > 0 \n",
    "\n",
    "def standard_scaler(X):\n",
    "    mean = X.mean(0)\n",
    "    sd = X.std(0)\n",
    "    return (X - mean)/sd"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "The perceptron is implemented below. As usual, we optionally standardize and add an intercept term. Then we fit $\\bbetahat$ with the algorithm introduced in the {doc}`concept section </content/c3/s2/perceptron>`. \n",
    "\n",
    "This implementation tracks whether the perceptron has converged (i.e. all training algorithms are fitted correctly) and stops fitting if so. If not, it will run until `n_iters` is reached. "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {},
   "outputs": [],
   "source": [
    "class Perceptron:\n",
    "\n",
    "    def fit(self, X, y, n_iter = 10**3, lr = 0.001, add_intercept = True, standardize = True):\n",
    "        \n",
    "        # Add Info #\n",
    "        if standardize:\n",
    "            X = standard_scaler(X)\n",
    "        if add_intercept:\n",
    "            ones = np.ones(len(X)).reshape(-1, 1)\n",
    "        self.X = X\n",
    "        self.N, self.D = self.X.shape\n",
    "        self.y = y\n",
    "        self.n_iter = n_iter\n",
    "        self.lr = lr\n",
    "        self.converged = False\n",
    "        \n",
    "        # Fit #\n",
    "        beta = np.random.randn(self.D)/5\n",
    "        for i in range(int(self.n_iter)):\n",
    "            \n",
    "            # Form predictions\n",
    "            yhat = to_binary(sign(np.dot(self.X, beta)))\n",
    "            \n",
    "            # Check for convergence\n",
    "            if np.all(yhat == sign(self.y)):\n",
    "                self.converged = True\n",
    "                self.iterations_until_convergence = i\n",
    "                break\n",
    "                \n",
    "            # Otherwise, adjust\n",
    "            for n in range(self.N):\n",
    "                yhat_n = sign(np.dot(beta, self.X[n]))\n",
    "                if (self.y[n]*yhat_n == -1):\n",
    "                    beta += self.lr * self.y[n]*self.X[n]\n",
    "\n",
    "        # Return Values #\n",
    "        self.beta = beta\n",
    "        self.yhat = to_binary(sign(np.dot(self.X, self.beta)))\n",
    "                    "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Now we can fit the model. We'll again use the {doc}`breast cancer </content/appendix/data>` dataset from `sklearn.datasets`. We can also check whether the perceptron converged and, if so, after how many iterations."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "metadata": {},
   "outputs": [],
   "source": [
    "perceptron = Perceptron()\n",
    "perceptron.fit(X, y, n_iter = 1e3, lr = 0.01)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Not converged\n"
     ]
    }
   ],
   "source": [
    "if perceptron.converged:\n",
    "    print(f\"Converged after {perceptron.iterations_until_convergence} iterations\")\n",
    "else:\n",
    "    print(\"Not converged\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "metadata": {},
   "outputs": [
    {
     "data": {
      "text/plain": [
       "0.9736379613356766"
      ]
     },
     "execution_count": 6,
     "metadata": {},
     "output_type": "execute_result"
    }
   ],
   "source": [
    "np.mean(perceptron.yhat == perceptron.y)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.6"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 4
}
